/*
 * =====================================================================================
 *
 *       Filename:  3637radixSort.c
 *
 *    Description:  use radix sort
 *
 *        Version:  1.0
 *        Created:  2012年06月29日 17时09分27秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:
 *
 * =====================================================================================
 */

#include	<stdio.h>

#define	 T short			/*  */

T dumpArr[20004];
T array[20004];
T digitArr[20004];

const int devided[] = {1, 10, 100, 1000, 10000, 100000, 1000000};

T* radixsort(T *x, T *y, int n, int digit)
{
    int i = 0, k = 0;
    int v;
    short c[10] = {0x00};
    T *dst = x, *src = y, *pTmp;
    for (i = 1; i <= digit; ++i)
    {
        pTmp = src;
        src = dst;
        dst = pTmp;

        for (k = 0; k < n; ++k)
        {
            v = (src[k]/devided[i-1]) - (src[k]/devided[i] * 10);
            ++c[v];
            digitArr[k] = v;
        }

        for (k = 1; k < 10; ++k)
            c[k] += c[k-1];

        for (k = n-1; k >= 0; --k)
        {
            //v = (src[k]/devided[i-1]) - (src[k]/devided[i] * 10);
            v = digitArr[k];
            dst[c[v]-1] = src[k];
            --c[v];
        }

        for (k = 0; k < 10; ++k)
            c[k] = 0;

//        printf ( "after the %d cycle\n", i);
//        for (k = 0; k < n; ++k)
//            printf ( "%hd\t", dst[k]);
//        printf ( "\n" );
    }
    return dst;
}


T* radixsort_hex(T *x, T *y, int n, int digit)
{
    int i = 0, k = 0;
    unsigned int v;
    short c[16] = {0x00};
    T *dst = x, *src = y, *pTmp;
    int *countPtr;
    int shift = 0;
    for (i = 1; i <= digit; ++i)
    {
        pTmp = src;
        src = dst;
        dst = pTmp;

        for (k = 0; k < n; ++k)
        {
            v = (src[k] >> shift) & 0x0f;
            ++c[v];
        }

        for (k = 1; k < 16; ++k)
            c[k] += c[k-1];

        for (k = n-1; k >= 0; --k)
        {
            v = (src[k] >> shift) & 0x0f;
            //cache hit low
            dst[c[v]-1] = src[k];
            --c[v];
        }

        shift += 4;

        for (k = 0; k < 16; ++k)
            c[k] = 0;

//        printf ( "after the %d cycle\n", i);
//        for (k = 0; k < n; ++k)
//            printf ( "%hd\t", dst[k]);
//        printf ( "\n" );
    }
    return dst;
}
int main(int argc, char *argv[])
{
    int times, items_count;
    int total_discount;
    int idx, off;
    //int max = -1, maxdigit = 5;
    T *ptr;

    scanf("%d", &times);
    while (times--)
    {
//        max = -1; maxdigit = 0;
        scanf("%d", &items_count);
        for (idx = 0; idx < items_count; ++idx)
        {
            scanf("%hd", &array[idx]);
//            if (array[idx] > max)
//                max = array[idx];
        }
//        while ((max / devided[maxdigit]))
//            ++maxdigit;
        ptr = radixsort_hex(array, dumpArr, items_count, 4);
        total_discount = 0;
        off = items_count - 3;
        while (off >= 0)
        {
            total_discount += ptr[off];
            off -= 3;
        }
        printf ( "%d\n", total_discount);
    }
    return 0;
}
